//
//  Find.hpp
//  DataStructure
//
//  Created by 劢克科技 on 2020/8/10.
//  Copyright © 2020 Shuleiming. All rights reserved.
//

#ifndef Find_hpp
#define Find_hpp

#include <stdio.h>

// ***** ASL Average Search Length *****
// 反映了查找算法时间复杂度

// *** 顺序查找(“哨兵“) ***
// O(n)
// 查找成功ASL: (1+2+...+n) / n = (n+1)/2
// 查找失败ASL：n+1

// 问：查找失败ASL不应该是 1/n(n+n+n...)=n么？
// 答：是的，但是在“哨兵”模式中，比较次数为n+1，因为arr[0]也需要被比较一次.

// ** 对于有序表，可以进行优化 **
// 优化查找失败
// 查找成功ASL: (1+2+...+n) / n = (n+1)/2
// 查找失败ASL：n/2 + n/(n+1)
// ** 被查找的概率不等 **
// 把被查找概率大的元素放到前面，优化查找成功
int Search_Seq1(int arr[], int len, int key)
{
    int i;
    arr[0] = key; // 0号位置作为”哨兵“
    for (i = len; arr[i] != key; i--);
    return i;
}

// ***** 折半查找 *****
// 需要升序或者降序，适用于有序顺序表
// 时间复杂度：O(log2n)
// 折半查找判定树的构造：右子树结点 - 左子树结点 = 0或1
// 一定是平衡二叉树,h >= log2(n+1)
// ASL <= h
// 折半查找不一定比顺序查找更优秀！
int Search_Mid2(int arr[], int len, int key)
{
    int low = 0, high = len - 1, mid = 0;
    while (low <= high) {
        mid = (low+high) / 2;
        if (arr[mid] == key) {
            break;
        } else if (arr[mid] > key) {
            high = mid - 1;
        } else {
            low = mid + 1;
        }
    }
    return low <= high ? mid : -1;
}

// *** 分块查找 ***
// 又称为索引顺序表；块内无序，块间有序
// ASL成功分析
// n个元素分为b块，每一块中有s个元素
// 用顺序查找索引表，ASL = L1 + Ls
// L1 = (1+2+...+b)/b = (b+1) / 2
// Ls = (1+2+...+s)/s = (s+1) / 2
// ASL = L1 + Ls = (s^2+2s+n)/2s, 当s=sqrt(n)时，ASLmin = sqrt(n)+1
// 所以最好的分块为s = sqrt(n)

// B树的定义
typedef struct BNode {
    int key[4]; // 最多4个关键字
    struct BNode *childs[5]; // 最多5个关键字
    int num; // 节点中有几个关键字
} BTree;

// ***** B树(Balance Tree!) *****
// 又称为多路平衡查找树
// ✨m叉查找树中保证查找效率：（m叉 = m阶）
// 1. m叉查找树中，除了跟结点外，至少有m/2向上取整个子树
// 2. 任何结点所有子树的高度相同
// 3. 根结点子树数[2,m],关键字数[1,m-1]
// ✨4. n个关键字对应n+1个分叉
// 满足1和2则称之为B树
// ✨B树的高度的计算
// B树的叶子节点 = 失败节点
// B树最后一层节点 = 终端节点
// n个关键字的m阶B树有n+1个叶子结点(n个结点分割为n+1个区域)
// B树的插入和删除

// *** B+树 ***
// 1.每个分支，最多有m棵子树
// 2.非叶根结点最少有2棵子树，其他每个结点至少有m/2上取整棵
// ✨3.n个关键字对应n个分叉
// 4.叶子结点包含全部关键字，从大到小排列
// 5.B+树的结点中，仅仅起到索引作用，信息储存在叶子结点的指针中
// B+树的非叶子结点不包含记录的存储地址，使得1个磁盘块可以包含更多关键字，减少磁盘I/O

// ***** 散列查找 *****
// 查找长度：对比关键字的次数
// ASL失败 = 装填因子a = 表中记录数 / 散列表长度

// *** 除留余数法 ***
// H(key) = key % p，散列表长m，p为不大于m的质数或者为接近m的质数
// 使用质数取模，分布更均匀，参考《数论》

// *** 直接定址法 ***
// 适用于关键字分布基本连续的情况
// H(key) = a * key + b，不会产生冲突

// *** 数字分析法 ***
// 选取数码分布均匀的若干位作为散列地址，如电话号码后四位。

// *** 平方取中法 ***
// 适用于每位都不均匀，或者长度小于散列表地址所需位数，如身份证号码

// **** 拉链法 ****
// H(key) = key % p

// ***** 开放定址法 *****
// H(key) = key % p
// Hi = (H(key) + di) % m，di代表第i次冲突
// 1. 线性探测法：di=0,1,2...，容易造成”聚集现象“（喜欢考^_^）
// 删除中间的元素时，用bool标记
// 2. 平方探测法：di=0^2,1^2,-1^2,2^2,-2^2...，不容易造成堆积
// 平方探测法长度m必须为4j+3的质数
// 删除时，只能标志元素为空，不能真正删除，否则会影响查找

// ** 再散列法 **
// 散列函数冲突时，使用下一个散列函数计算直到不冲突为止。

#endif /* Find_hpp */
